package violentRecursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * @author kunkun
 * @className LeetCode_32
 * @Description ...
 * @date 2025/3/18 11:21
 */
public class LeetCode_32 {
    public int longestValidParentheses(String s) {
        return solution_1(s);
    }

    //1. 动态规划
    private int solution_1(String str) {
        if (str.length()==0){
            return 0;
        }
        //1. 定义dp数组，和初始值
        int[] res = new int[str.length()];
        res[0] = 0;

        //2. for循环，根据状态转移方程，填入数值
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i)=='('){
                res[i]=0;
            }else {
                int index = i-res[i-1]-1;
                if (index>=0 && str.charAt(index)=='('){
                    res[i]=2+res[i-1]+((index>=1)?res[index-1]:0);
                }else{
                    res[i]=0;
                }
            }
        }
        //3. 返回最大值
        int max =-1;
        for (int i = 0; i < res.length; i++) {
            if (res[i]>max){
                max = res[i];
            }
        }
        return max;

    }


}
